package Offer.offer2016;

import domain.TreeNode;

public class Test06 {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode result = constructBinaryTree(pre, in);
        System.out.println(result);

    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0) {
            return null;
        }
        return reConstructBinaryTree(pre, 0, in, 0, pre.length - 1);
    }

    public static TreeNode reConstructBinaryTree(int[] pre, int index, int[] in, int start, int end) {
        if (start > end)
            return null;
        TreeNode root = new TreeNode();
        root.val = pre[start];
        if (start == end)
            return root;
        int i = 0;
        for (i = start; i <= end; i++) {
            if (in[i] == root.val) {
                break;
            }
        }
        root.left = reConstructBinaryTree(pre, index + 1, in, start, i - 1);
        root.right = reConstructBinaryTree(pre, index - start + i + 1, in, i + 1, end);

        return root;
    }

    /**
     * ������������ͺ������ �õ����Ľṹ
     */

    public static TreeNode constructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length <= 0 || in.length <= 0) {
            return null;
        }
        return constructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);

    }

    public static TreeNode constructBinaryTree(int[] pre, int prestart, int preend, int[] in, int instart, int inend) {
        if (prestart > preend || instart > inend) {
            return null;
        }
        TreeNode tmp = new TreeNode();
        tmp.val = pre[prestart];
        if (prestart == preend && instart == inend) {
            return tmp;
        }
        int rootIndex = -1;
        for (int i = instart; i <= inend; i++) {
            if (in[i] == pre[prestart]) {
                rootIndex = i;
                break;
            }
        }
        if (rootIndex == -1) {
            return null;
        } else {
            tmp.left = constructBinaryTree(pre, prestart + 1, prestart + rootIndex - instart, in, instart, instart + rootIndex - 1);
            tmp.right = constructBinaryTree(pre, prestart + rootIndex - instart + 1, preend, in, rootIndex + 1, inend);
        }
        return tmp;
    }
}
